|
In computer science, a simple precedence parser is a type of bottom-up parser for context-free grammars that can be used only by simple precedence grammars. The implementation of the parser is quite similar to the generic bottom-up parser. A stack is used to store a viable prefix of a sentential form from a rightmost derivation. Symbols , and are used to identify the pivot, and to know when to Shift or when to Reduce. ==Implementation== * Compute the Wirth–Weber precedence relationship table. * Start with a stack with only the starting marker $. * Start with the string being parsed (Input) ended with an ending marker $. * While not (Stack equals to $S and Input equals to $) (S = Initial symbol of the grammar) * * Search in the table the relationship between Top(stack) and NextToken(Input) * * if the relationship is or * * * Shift: * * * Push(Stack, relationship) * * * Push(Stack, NextToken(Input)) * * * RemoveNextToken(Input) * * if the relationship is * * * Reduce: * * * SearchProductionToReduce(Stack) * * * RemovePivot(Stack) * * * Search in the table the relationship between the Non terminal from the production and first symbol in the stack (Starting from top) * * * Push(Stack, relationship) * * * Push(Stack, Non terminal) SearchProductionToReduce (Stack) * search the Pivot in the stack the nearest from the top * search in the productions of the grammar which one have the same right side than the Pivot 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「simple precedence parser」の詳細全文を読む スポンサード リンク
|